This invention relates to the field of digital communications, and is particularly concerned with improving error rate performance and increasing the transmission rate of convolutionally encoded data transmissions.
Turbo-codes have received considerable attention in recent years due to their powerful error correcting capability, reasonable complexity, and flexibility in terms of providing different block sizes and code rates. The original paper on xe2x80x9cTurbo-codesxe2x80x9d was published by C. Berrou, A. Glavieux, and P. Thitamajshima and was entitled xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, Proceedings of ICC""93, Geneva, Switzerland, pp. 1064-1070, May, 1993. (Also, see C. Berrou, and A. Glavieux, xe2x80x9cNear Optimum Error Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, IEEE Trans. On Comm., Vol. 44, No. 10, October 1996 and B. Talibart and C. Berrou, xe2x80x9cNotice Preliminaire du Circuit Turbo-Codeur/Decodeur TURBO4xe2x80x9d, Version 0.0, June 1995, and also U.S. Pat. No. 5,446,747.) A rate xc2xd binary code was represented that provides performance within 0.5 dB of the antipodal signaling capacity limit at a BER of 10xe2x88x925. The canonical Turbo encoder consisted of two rate xc2xd recursive systematic convolutional (RSC) encoders operating in parallel with the data bits interleaved between the two encoders. Soft-in soft-out iterative processing based on a posteriori probability (APP) decoding principles was used. This is also referred to as maximum a posteriori (MAP) decoding in the literature. The interleaver block size used was 65,536. It is practical to look at much shorter block sizes, on the order of a few hundred bits, where the overhead associated with flush bits becomes important.
A problem that was recognized early in the design of Turbo-codes is the termination of the trellises as noted by P. Robertson in xe2x80x9cIlluminating the Structure of Code and Decoder of Parallel Concatenated Recursive systematic (Turbo) Codesxe2x80x9d, IEEE Globecom, pp. 1298-1303, November-December, 1994. As with conventional block-oriented non-recursive convolutional codes, it is desirable to have the encoder start and stop in a known state. This is achieved for non-recursive convolutional codes by starting the encoder in a known state (usually the zero state) and then using known flush bits to terminate the encoder. The flush bits are usually zeros to force the encoder back into the zero state (zero-flush). The result is a simple decoder, with all bits well protected, but the flush bits take energy away from the data bits and also lower the code rate or bandwidth efficiency of the code. One solution to this problem is to perform tail-biting as noted by G. Solomon and H. Tilborg in xe2x80x9cA Connection Between Block and Convolutional Codesxe2x80x9d, SIAM J. Appl. Math, Vol. 37, No. 2, pp. 358-369, October, 1979; and by H. Ma and J. Wolf in xe2x80x9cOn Tail Biting Convolutional Codesxe2x80x9d, IEEE Trans. on Comm., Vol. COM-34, No. 2, pp. 104-111, February, 1986. Tail biting is a technique where the constraint length k (memory k-1) encoder is initialized with the first k-1 data bits and then flushed at the end of the block with the same k-1 data bits. This eliminates the overhead associated with the flush bits. In this case the starting and ending states are the same, but unknown. Decoding requires more computations, but the increase in complexity is not significant for typical block sizes of several Viterbi decoder history depths. The usual close-to-optimal decoding approach is to decode in a circle, processing at least two extra history depths of signal as noted by Solomon and Tilborg in their previously noted work.
The termination problem is more complicated for Turbo-codes. This is because there are (at least) two trellises to be terminated and the input to the second RSC encoder is an interleaved or permuted version of the input to the first RSC encoder. The most common termination approach is to add termination bits to the end of the first uninterleaved block, resulting in termination of the first trellis, but leave the second trellis unterminated. The first encoder cannot be simply flushed with zero bits because the encoder is recursive. It is straightforward, however, to determine the termination bits required to force the encoder into a given state, such as the zero state. The required termination bits are simply the feedback bits from the RSC encoder at the time of termination.
Termination of both trellises has been achieved by P. Guinand and J. Lodge as documented in xe2x80x9cTrellis Termination for Turbo Encodersxe2x80x9d, Proc. 17th Biennial Symp. On Communications, Queen""s University, Kingston, Canada, pp. 389-392, May 30-Jun. 1 1994. This was accomplished by determining a set of termination positions in the input that allow control of both final states and then defining the appropriate mapping to determine the bits to be inserted into these positions. Conceptually this involves running the encoder twice (at most) and does add further overhead in the form of yet more termination bits.
An alternate solution to the problem of terminating the second trellis is the so-called frame-oriented Turbo-code of C. Berrou and M. Jezequel as described in xe2x80x9cFrame-Oriented Convolutional Turbo Codesxe2x80x9d, Elec. Letters, Vol.32, No.15, pp. 1362-1364, July 1996. In this approach, a single trellis is used. A block of input bits, twice as long as the number of data bits, is produced by placing the data bits, in their original order, in the first half of the block and a specially interleaved or permuted copy of the data bits in the second half of the block. This block is then run through a single RSC encoder to generate the parity bits. There are some similarities between this approach and a tail-biting approach in that the flush bits are eliminated without leaving an unterminated end, but full tail biting is not performed. Also, the block size is restricted to be a multiple of the repetition period of the RSC feedback polynomial. For example, the Turbo4 encoder defined in B. Talibart and C. Berrou has a repetition period of 15. This is an undesirable restriction, and represents a significant overhead for some desired block lengths. Full tail biting in this situation would result in an increase in the code rate.
Other tail-biting methods have been mentioned in various papers such as J. Anderson and S. Hladik""s xe2x80x9cMAP Tail biting Decodersxe2x80x9d, ISIT, Ulm, Germany, p. 224, Jun. 29-Jul. 4 1997, J. Anderson and S. Hladik""s , xe2x80x9cTail biting MAP Decodersxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, pp. 297-302, February 1998, Y-P Wang, R. Ramesh, A. Hassan, and H. Koorapaty""s, xe2x80x9cOn MAP Decoding for Tail-Biting Convolutional Codesxe2x80x9d, ISIT, Ulm, Germany, p. 225, Jun. 29-Jul. 4 1997, H-A Loeliger""s, xe2x80x9cNew Turbo-Like Codesxe2x80x9d, ISIT, Ulm, Germany, p. 109, Jun. 29-Jul. 4, 1997. None of these schemes is particularly general and/or flexible. The Anderson and Hladik papers make no mention of how to implement tail-biting RSC codes or tail-biting Turbo-codes. Tail-citing Turbo-codes are mentioned in Wang, Ramesh, Hassan and Koorapaty, as well as in H-A Loeliger but these papers place restrictions on the feedback polynomial and block length of the tail-biting RSC component codes. These restrictions, though undesirable, are necessary because these codes are designed to be strictly systematic, that is, all the data bits are encoded and represented directly in the systematic output of the code.
In the following discussion, various known method of either terminating or tail biting the output of a Turbo encoder will be discussed. In the discussion, the term xe2x80x9csymbolxe2x80x9d will be used to refer to either a bit or an arbitrary non-binary symbol. The associated RSC and Turbo decoders are also described. One can consider the number of data or information bits per block to be K and the total number of code bits is N. Thus, the exact code rate for a block Turbo-code is always r=K/N. The memory of each RSC encoder is typically the same and given by m=kxe2x88x921, where k is the RSC encoder constraint length. In some cases the m parameter will be used to represent a value less than or equal to the memory of kxe2x88x921. In most cases the Turbo encoder is constructed from two RSC encoders though extensions to more than two RSC encoders are also made. Binary rate xc2xd RSC encoders are also generally assumed, but the various approaches are not restricted to rate xc2xd RSC codes of to binary symbols (bits).
One method is to use two unterminated RSC codes as is illustrated in FIG. 1. In this case, both RSC encoders start in the zero-state (or any known state) and are left unterminated in an unknown state after the K data bits are encoded. The data bits are interleaved prior to entering the second RSC encoder, so that two different permutations of the data are used, the first typically being the identity permutation (no interleaving).
One problem with this approach is that the end bits are poorly protected. A good interleaver would ensure that bits near the end of the first permutation are not near the end of the second permutation, but even so, the end bits still have less protection than the other bits. The opposite is true for the start bits. These bits are overly protected because of the known starting state. With an RSC code rate of xc2xd, the overall unpunctured Turbo-code rate is ⅓. This is because the data bits are only sent over the channel once. Other Turbo-code rates are also possible with different starting RSC code rates and puncturing.
Another approach is to use one terminated and one unterminated RSC code as illustrated in FIG. 2. This method is the most common approach found in the literature. In this case, the first RSC encoder starts in the zero state, and m termination bits are added to the K data bits to force the first RSC encoder to also stop in the zero state. The termination bit values are uniquely determined by the state of the first RSC encoder after the last data bit. The termination bits are easily calculated to match the feedback as required, or they can be precalculated for each possible encoder state and stored in a table. The resulting K+m bits are then interleaved and sent to the second RSC encoder. Note that the m termination bits (denoted by xe2x80x9ctxe2x80x9d in FIG. 2) are included in the interleaver. The second RSC encoder also starts in the zero state but is left unterminated in an unknown state after the K+m interleaved bits are encoded. This approach typically works better than the previous approach because fewer bits are near an unterminated end. Of course, the bits near the end of the second permutation still receive less protection than the other bits. Another drawback is the reduced code rate, due to the addition of the termination bits. With an RSC code rate of xc2xd the overall unpunctured Turbo-code rate is K/(3(K+m)). For example, with K=100 and m=4, the code rate is 0.321.
Yet another approach is to use two terminated RSC Codes as shown in FIG. 3. This method was first introduced by Guinand and Lodge and it is highly effective for large data blocks. In this case, both RSC encoders start in the zero state, and 2m termination bits are added to the K data bits to force both encoders to also end in the zero state. A summary of this prior art method is as follows.
Given a specific block size (including room for 2m termination bits, denoted b xe2x80x9ctxe2x80x9d in FIG. 3) and a specific interleaver, the first step is to find a set of termination positions within the input data block that can be used to force the ending states of both RSC encoders to be zero. The total ending state (the ending states of both RSC encoders) is defined by a linear mapping from the K+2m input bits to the 2m bits defining the total ending state. Let the rank of this mapping matrix to be denoted by rank. In general rank will be less than or equal to 2m, with the rank achieving its maximum value for most encoders and interleavers of interest. It is assumed that rank=2m in the following discussion, but this is not necessary. Any rank linearly independent columns of the mapping matrix span the range of the linear map. Thus, the total ending state can be forced to zero by selecting the appropriate inputs for these rank columns of the mapping matrix. In general, the last rank positions may not be linearly independent. However, the last m positions will correspond to linearly independent columns of the matrix. Finding the remaining m positions uses a search procedure involving sending impulse signals into the dual RSC encoder and observing the output to see if the resulting total ending state is linearly independent of the total ending states already found. This procedure is continued until one has rank linearly independent total ending states. Note that the determination of the 2m positions is independent of the input data so that this step only needs to be performed during the initial code design. The inverse of the rank-by-rank matrix mapping the termination bits to the total ending state of the dual RSC encoder can also be precomputed. More details are given in Guinand and Lodge""s paper.
Encoding can then be performed as follows. First, the data bits are placed into the non-termination positions of the uninterleaved input block, and the termination positions are filled with zeros. This block is interleaved and the two permutations are passed through the dual RSC encoder. Multiplying the total ending state by the inverse matrix described above gives the termination bits to be inserted into the termination positions. After inserting the termination bits into both permutations, the dual RSC encoder is run again to obtain the final encoded sequence.
The termination positions are not uniquely defined. There are many possible choices for a set of termination positions. If the positions are chosen close to the end of the uninterleaved block, as shown in FIG. 3, then the second encoding of the uninterleaved block can be simplified. That is, the first RSC encoder can start its second pass at the first non-zero termination bit, which is near the end of the block. The second RSC encoder can also start its second pass at the first interleaved non-zero termination bit, but the reduction in processing will typically be small because the termination positions will be spread throughout the interleaved block. Thus, the dual termination Turbo encoder typically requires about 50% more processing than the conventional Turbo encoder. This is of little consequence since the processing required by the Turbo decoder typically overshadows that required by the Turbo encoder. Table lookup techniques can also be used to trade off memory for processing in the encoder.
The advantage of the dual termination method over the previous methods is that all bits now have good protection. The disadvantage is that the code rate is reduced even further, due to the use of 2m termination bits. With an RSC code rate of xc2xd the overall unpunctured Turbo-code rate is K/(3(K+2m)). For example, with K=100 and m=4, the code rate is 0.309.
As mentioned earlier, another solution to the problem of terminating the second trellis is the so-called frame-oriented Turbo-code of C. Berrou and M. Jezequel. In this approach a single trellis is used that both starts and ends in the zero state. A block of input bits twice as long as the number of data bits is produced by placing the data bits, in their original order, in the first half of the block and a specially interleaved copy of the data bits in the second half of the block. This block is then run through a single RSC encoder to generate the parity bits. The final termination of the trellis is a result of a special interleaver structure. If p is the repetition of the RSC encoder, then the block size is restricted to be a multiple of p. The repetition period of an RSC encoder is determined by the feedback polynomial. Good choices for the feedback polynomial appear to be those that generate maximal-length sequences, also called m-sequences. Thus, the repetition period is usually given by p=2mxe2x88x921 for good RSC encoders. For example, the Turbo4 encoder defined in B. Talibart and C. Berrou has a repetition period of p=15. This is an undesirable restriction, and may represent a significant overhead for some desired block sizes. The interleaver design is also restricted such that the two occurrences of each systematic bit must be a multiple of p apart. It is this restriction that forces the encoder back into the zero state once every systematic bit has been encountered twice. This is also an undesirable constraint on the interleaver.
With respect to Turbo decoding, some prior art tail-biting methods have been mentioned in various papers such as J. Anderson and S. Hladik""s xe2x80x9cMAP Tail biting Decodersxe2x80x9d, ISIT, Ulm, Germany, p. 224, Jun.29-Jul. 4, 1997, J. Anderson and S. Hladik, xe2x80x9cTail biting MAP Decodersxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, pp. 297-302, February 1998, Y-P Wang, R. Ramesh, A. Hassan, and H. Koorapaty, xe2x80x9cOn MAP Decoding for Tail-Biting Convolutional Codesxe2x80x9d, ISIT, Ulm, Germany, p. 225, Jun. 29-Jul. 4, 1997, H-A Loeliger, xe2x80x9cNew Turbo-Like Codesxe2x80x9d, ISIT, Ulm, Germany, p. 109, Jun. 29-Jul. 4, 1997. As mentioned earlier, none of these schemes is particularly general and/or flexible. Two tail-biting MAP decoding algorithms are described in the Anderson and Hladik papers previously mentioned. The first algorithm is a true MAP decoder for tail-biting blocks, and is very complicated. The second Algorithm is more practical, and performs MAP decoding in a circle with overlap, analogous to the overlap method used for the Viterbi decoding of non-recursive convolutional tail-biting block codes.
An object of this invention is to provide an improved data transmission rate in digital communications, using turbo codes.
It is another object of this invention to provide tail biting on a plurality of RSC encoders within a Turbo encoder without requiring extra termination bits.
It is yet another object of this invention to provide a method of terminating the RSC encoders within a Turbo encoder such that it provides a more evenly distributed degree of protection across the entire block of data.
It is a further object of this invention to provide an improved turbo encoding scheme, tuned for shorter block lengths that is based upon a plurality of trellises and recursive systematic convolutional (RSC) coding with more flexibility in selecting a block length and interleaver design.
It is also an object of this invention to provide a relatively flexible and simplified method of decoding tail biting Turbo encoded data.
Unlike the schemes presented by Wang, Ramesh, Hassan and Koorapaty in xe2x80x9cOn MAP Decoding for Tail-Biting Convolutional Codesxe2x80x9d, ISIT, Ulm, Germany, p. 225, Jun. 29-Jul. 4, 1997, or Loeliger in xe2x80x9cNew Turbo-Like Codesxe2x80x9d, ISIT, Ulm, Germany, p. 109, Jun. 29-Jul. 4, 1997, the scheme presented here is both general and flexible. Two tail biting maximum a priori (MAP) decoding algorithms are described by Anderson and Hladik in, xe2x80x9cMAP Tailbiting Decodersxe2x80x9d, ISIT, Ulm, Germany, p. 224, Jun. 29-Jul. 4, 1997, and in, xe2x80x9cTailbiting MAP Decodersxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 16, No. 2, pp. 297-302, February, 1998. The first algorithm, a true MAP decoder for tail-biting blocks, is very complicated. The second algorithm is more practical, and performs MAP decoding in a circle with overlap, analogous to the overlap method used for the Viterbi decoding of non-recursive convolutional tail-biting block codes. The Anderson and Hladik papers make no mention of how to implement tail-biting RSC codes or tail-biting Turbo-codes. Tail-biting Turbo-codes are mentioned in Wang, Ramesh, Hassan and Koorapaty, as well as in Loeliger. These papers place restrictions on both the feedback polynomial and block length of the tail-biting RSC component codes. These restrictions are necessary because these codes are designed to be strictly systematic, that is, all the data bits are encoded and represented directly in the systematic output of the code. These restrictions do not apply to the new tail-biting approaches presented here because, among other reasons, these new tail-biting turbo-codes are not strictly systematic.
A new tail-biting frame-oriented Turbo-code is also described. The advantage over the original frame-oriented Turbo-code is that the code rate is increased, due to the inclusion of m extra data bits. The disadvantage is that now a full tail-biting Turbo decoder is required. This only increases the decoding complexity slightly. The complexity of the encoder is not increased in this case. With an RSC code rate of xc2xd the overall unpunctured Turbo-code rate is K/(3(Kxe2x88x92m)), where K-m must be a multiple of p. For example, with m=4,p=15, and K=124, the unpunctured code-rate is 0.344.
In accordance with a first aspect of the current invention there is provided a method of encoding a raw data set of ordered symbols comprising the steps of first, providing a recursive systematic convolutional (RSC) encoder. The second step is to divide the raw data set into first and second data subsets. The third step is to use the first data subset to determine a starting state for the RSC encoder, such that the starting state uniquely corresponds to the first data subset. The fourth step is to use the starting state determined in the third step to initialize the RSC encoder. The fifth step is to derive a systematic set from the first and second data subsets. The sixth step is to encode the systematic set using the RSC encoder to generate a parity set of ordered symbols. The first embodiment of the first aspect of this invention defines that the RSC encoder has a memory size not less than 1, the raw data set and the systematic set each have K ordered symbols, the first and second data subsets have cardinalities of m and K-m respectively, where 1≲m≲ xe2x80x9cmemory size of the RSC encoderxe2x80x9d, and adds the following steps to the method of the first aspect. The seventh step is to define a position set of K ordered positions to be filled with the systematic set. The eighth step is to divide the position set into first and second position subsets having cardinalities of m and K-m respectively, such that each position in the first subset independently influences an ending state of the RSC encoder upon completion of the encoding step, when it is filled with a symbol from the systematic data set. The ninth step is to fill the second position subset with the elements from the second data subset to form a portion of the systematic set. The tenth step is to use the starting state, the first position subset and the portion of the systematic set, determined in step eight, to determine a tail-biting set of m ordered symbols, such that the tail-biting set forces the ending state to be the same as the starting state. The eleventh step is to fill the first position subset with the tail-biting set to complete the systematic set contained in the position set. This process will force the ending state to be the same as the starting state upon completion of the encoding step. The second embodiment of the first aspect adds an additional four steps, and may be applied to either the initial aspect, or the embodiments thereof. The first additional step is to define the first permutation as being the same as the systematic set. The second additional step is to generate at least one further permutation of the systematic set. The third additional step is to provide at least one further systematic convolutional encoder. The fourth additional step is to encode the at least one further permutation using the at least one further encoder to generate at least one other parity set of ordered symbols. In addition, all embodiments of the first aspect of the invention can be modified by the addition of at least one further convolutional encoder, wherein the encoding step uses the RSC encoder operating in series with the further encoder.
In accordance with a second aspect of the current invention, a method of encoding a raw data set of K ordered symbols is defined to comprise the following steps. The first step is to provide a plurality P of recursive systematic convolutional (RSC) encoders each having a memory size not less than 1. The second step is to provide P-1 interleavers that each interleave K ordered symbols. The third step is to divide the raw data set of ordered symbols into first and second data subsets of cardinalities M and K-M respectively, where M is at least one and at most the sum of the memory sizes of the P RSC encoders. The fourth step is to determine a vital starting state consisting of P individual starting states which correspond to the P RSC encoders from the first data subset, such that the total starting state uniquely corresponds to the first data subset. The fifth step is the initialization of the P RSC encoders with the corresponding P individual starting states that were determined in step four. The sixth step is to define a position set of K ordered positions to be filled with a systematic set. The seventh step is to divide the position set into first and second position subsets of cardinalities M and K-M respectively, based on the P-1 interleavers, such that each position in the first position subset when filled with a symbol from the systematic set independently influences a total ending state consisting of P individual ending states corresponding to the P RSC encoders. The eighth step is to fill the second position subset with the second data subset to form a portion of the systematic set. The ninth step is to use the total starting state, the first position subset, portion of the systematic set determined in step eight, and the P-1 interleaves to determine a tail-biting set, of cardinality M, such that the tail-biting set forces the total ending state to be the same as the total starting state. The tenth step is to fill the first position subset with the tail-biting set, to complete the systematic set contained in the position set. The eleventh step is to interleave the systematic set P-1 times using the P-1 interleavers to form P permutations. The twelfth step is to encode each of the P permutations, from step eleven, using a corresponding RSC encoder, from the P RSC encoders, to generate P respective parity sets of ordered symbols, thereby forcing the total ending state to be the same as the total starting state. In an embodiment of the present invention each of the P RSC encoders has a memory size of mn, for n=0. . . P-1, where mn is at least one and each of the P RSC encoders has an individual state defined respectively by an individual state set of mn ordered state symbols, for n=0. . . P-1, where M equals the sum of all values of mn, for n=0. . . P-1, and where a total state requires a total state set of M ordered state symbols.
In accordance with a third aspect of the current invention there is provided a method of encoding a raw data set of K ordered symbols comprising of the following 13 steps. The first step is to provide a recursive systematic convolutional (RSC) encoder having a memory size of at least one. The second step is to provide a plurality P-1 of ordered interleavers each for interleaving K ordered symbols. The third step is to divide the raw data set into first and second data subsets of cardinalities m and K-m, where 1≲m≲ xe2x80x9cmemory size of the RSC encoderxe2x80x9d. The fourth step is to determine a starting state for the RSC encoder from the first data subset, such that the starting state uniquely corresponds to the first data subset. The fifth step is to initialize the RSC encoder with the starting state determined in the fourth step. The sixth step is to define a position set, of cardinality K, to be filled with a systematic set. The seventh step is to divide the position set, defined in the sixth step, into first and second position subsets, of cardinalities m and K-m respectively, based on the P-1 interleavers, such that each position in the first position subset when filled with a symbol from the systematic set independently influences an ending state of the RSC encoder. The eighth step is to fill the second position subset with the second data subset, thereby forming a portion of the systematic set. The ninth step is to use the starting state, the first position subset, said portion of the systematic set, and the P-1 ordered interleavers to determine a tail-biting set, of cardinality m, such that the tail-biting set forces the ending state to be the same as the starting state. The tenth step is to fill the first position subset with the tail-biting set to complete the systematic set contained in the position set. The eleventh step is to interleave the systematic set P-1 times using the P-1 ordered interleavers to form P ordered permutations. The twelfth step is to form a contiguous block from the P ordered permutations created in step eleven. The thirteenth step is to encode the contiguous block, formed in step twelve, using the RSC encoder to generate P parity sets of ordered symbols, corresponding to the P ordered permutations, thereby forcing the ending state to be the same as the starting state.
In accordance with a fourth aspect of the current invention there is provided a method of encoding a raw data set of K ordered symbols comprising the following eight steps. The first step is to provide a recursive systematic convolutional (RSC) encoder having a memory size of at least one and a repetition period p. The second step is the division of the raw data set into first and second data subsets, of cardinalities, m and K-m respectively, where 1≲m≲ xe2x80x9cmemory size of the RSC encoderxe2x80x9d, and K-xe2x80x94m is a multiple of the repetition period, p. The third step is to use the first data subset to determine a starting state for the RSC encoder, such that the starting state uniquely corresponds to the first data subset. The fourth step is to use the starting state defined in the third step to initialize the RSC encoder. The fifth step is to define a position set of K-m ordered positions to be filled with the second data subset, thereby forming a systematic set. The sixth step is to provide a plurality P-1 of ordered interleavers for interleaving the systematic set P-1 times to form P ordered permutations of the systematic set, where P is a multiple of 2, such that each symbol in each permutation is paired with the same symbol in a different permutation at a distance of an integer multiple of p. The seventh step is to form a contiguous block from the P ordered permutations of step six. The eighth step is to encode the contiguous block of step seven using the RSC encoder to generate P parity sets of ordered symbols, corresponding to the P ordered permutations, thereby forcing an ending state to be the same as the starting state.
Embodiments of the first four aspects of the invention where ever applicable, may have m equal to the memory size of the RSC encoder, and the RSC encoder have a state defined by a state set of m ordered state symbols. Additionally further embodiments are defined wherein the state set required to define the starting state is determined directly from the first data subset, and, wherein the first data subset is extracted from the raw data set using the first position subset.
In accordance with a fifth aspect of the current invention there is provided a method of decoding a set of ordered samples representing a set of ordered symbols encoded according to the method described as the first aspect of the current invention, comprising two steps. The first step is to obtain an estimate of the starting state using a method of state estimation. The second step is to map the estimate of the starting state, obtained in step one, to an estimate of the first data subset. An embodiment of this fifth aspect of the current invention is to base the method of state estimation, used in the first step, on maximum likelihood state estimation.
In accordance with a sixth aspect of the current invention there is provided a method of decoding a set of ordered symbols encoded according to the method described in the first embodiment of the first aspect of the current invention, comprising three steps. The first step is to estimate the second data subset using a method of data estimation. The second step is to obtain an estimate of the starting state using a method of state estimation. The third step is to map the estimate of the starting state, obtained in the second step, to an estimate of the first data subset. Further embodiments of this aspect of the invention use, a method of data estimation based upon maximum likelihood sequence estimation with overlapped processing, a method of data estimation based on maximum a posteriori probability data estimation with overlapped processing, and a method of state estimation based on maximum likelihood state estimation with overlapped processing, either alone or in conjunction with each other.
In accordance with a seventh aspect of the current invention there is provided a method of decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the second aspect of the current invention, comprised of three steps. The first step is to estimate the second data subset using a method of iterative data estimation. The second step is to obtain an estimate of the total starting state, consisting of estimates of all individual starting states of the P RSC encoders, where each individual starting state estimate is determined using a method of state estimation. The third step is to map the estimate of the total starting state, obtained in the second step, to an estimate of the first data subset.
In accordance with an eighth aspect of the current invention there is provided a method of decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the third embodiment of the present invention, comprised of three steps. The first step is to estimate the second data subset using a method of iterative data estimation. The second step is to obtain an estimate of the starting state using a method of state estimation. The third step is to map the estimate of the starting state, obtain in step 2, to an estimate of the first data subset.
In accordance with a ninth aspect of the current invention there is provided a method of decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the fourth aspect of the current invention, comprised of three steps. The first step is to estimate the second data subset using a method of iterative data estimation. The second step is to obtain an estimate of the starting state using a method of state estimation. The third step is to map the estimate of the starting state, obtained in the second step, to an estimate of the first data subset.
The seventh, eighth, and ninth aspects all have embodiments that use, either one or both of the following modifications: a method of iterative data estimation that is based upon iterative a posteriori probability data estimation with overlapped processing, and a method of state estimation based upon maximum likelihood state estimation with overlapped processing.
In accordance with a tenth aspect of the current invention there is provided an apparatus for encoding a raw data set of ordered symbols comprised of three components. The first component is a recursive systematic convolutional (RSC) encoder. The second component is a buffer means for dividing the raw data set into first and second data subsets. The third component is a reset means for initializing the RSC encoder with a starting state based on the first data subset, such that the starting state uniquely corresponds to the first data subset, such that the RSC encoder encodes a systematic set derived form the first and second data subsets, to generate a parity set of ordered symbols. In an embodiment of this aspect of the present invention there is an encoder defining a first permutation as being the same as the systematic set, also consisting of a fourth and fifth component. The fourth component is an interleaver for generating a further permutation of the systematic set. The fifth component is a further systematic convolutional encoder for encoding said other permutation to generate a further parity set of ordered symbols. A further embodiment of this aspect of the invention is an encoder as described above further comprising a further convolutional encoder operating in series with the RSC encoder.
The enhancement of a decoding method for tail biting codes would facilitate increasing the data rate of communications systems, for small codeword length systems, by allowing the removal of flush bits while maintaining the docoder""s ability to correct errors due to noise.
In accordance with an eleventh aspect of the current invention there is provided an apparatus for encoding a raw data set of K ordered symbols comprised of four elements. The first element is a recursive systematic convolutional (RSC) encoder having a memory size of at least one. The second element is a buffer means for dividing the raw data set into first and second data subsets containing m and K-m ordered symbols respectively, where m is at least one and at most the memory size of the RSC encoder. The third element is a reset means for initializing the RSC encoder into a starting state based on the first data subset, such that the starting state uniquely corresponds to the first data subset. The fourth element is a tail-biting means for generating a tail-biting set of m ordered symbols based on the starting state, and the second data subset, such that the tail-biting set forces an ending state to be the same as the starting state, such that the RSC encoder encodes a systematic set consisting of a combination of the second data subset and the tail-biting set to generate a parity set of ordered symbols, thereby forcing the ending state to be the same as the starting state. An embodiment of the eleventh aspect of the current invention is an encoder as described above, wherein m equals the memory size of the RSC encoder, and the RSC encoder has a state defined by a state set of m ordered state symbols, such that the state set required to define the starting state is determined directly from the first data subset.
In accordance with a twelfth aspect of the current invention there is provided an apparatus for encoding a raw data set of K ordered symbols comprised of five elements. The first element is a plurality P of recursive systematic convolutional (RSC) encoders each having a memory size of at least one. The second element is P-1 interleavers each for interleaving K ordered symbols. The third element is a buffer means for dividing the raw data set into first and second data subsets containing M and K-M ordered symbols respectively, and for further subdividing the first data subset into P individual first data subsets containing mn ordered symbols, for n=0. . . P-1 where mn is at least one and at most the memory size of the n""th RSC encoder and where M is the sum of the P values of mm. The fourth element is a reset means for initializing each of the P RSC encoders into an individual starting state based on the corresponding individual first data subset, such that the individual starting state uniquely determines the individual first data subset. The fifth element is a tail-biting means for generating a tail-biting set of M ordered symbols based on a total starting state consisting of the individual starting states of the P RSC encoders, the second data subset, and the P-1 interleavers, such that the tail-biting set forces a total ending state consisting of individual ending states of the P RSC encoders to be the same as the total starting state, such that firstly each interleaver interleaves a systematic set consisting of a combination of the second data subset and the tail-biting set to form P permutations of the systematic set; and secondly each RSC encoder encodes one of said P permutations to generate P respective parity sets of ordered symbols, thereby forcing the total ending state to be the same as the total starting state. An embodiment of the twelfth aspect of the current invention is an encoder as described above wherein mn equals the memory size of the n""th RSC encoder, and n""th RSC encoder has an individual state defined by an individual state set of mn ordered state symbols, such that the n""th individual state set required to define the n""th individual starting state is determined directly from the n""th individual first data subset.
In accordance with a thirteenth embodiment of the current invention there is provided an apparatus for encoding a raw data set of K ordered symbols comprised of five elements. The first element is a recursive systematic convolutional (RSC) encoder having a memory size of at least one. The second element is a plurality P-1 of interleavers each for interleaving K ordered symbols. The third element is a buffer means for dividing the raw data set into first and second data subsets containing m and K-m ordered symbols respectively, where m is at least one and at most the memory size of the RSC encoder. The fourth element is a reset means for initializing the RSC encoder with a starting state based on the first data subset, such that the starting state uniquely corresponds to the first data subset. The fifth element is a tail-biting means for generating a tail-biting set of m ordered symbols based on the starting state, the second data subset, and the P-1 interleavers, such that the tail-biting set forces an ending state to be the same as the starting state, such that each interleaver interleaves a systematic set consisting of a combination of the second data subset and the tail-biting set to form P permutations of the systematic set and that the RSC encoder encodes a contiguous block consisting of said P permutations to generate P parity sets of ordered symbols, thereby forcing the ending state to be the same as the starting state. An embodiment of this thirteenth aspect is an encoder as described above, wherein m equals the memory size of the RSC encoder, and the RSC encoder has a state defined by a state set of m ordered state symbols, such that the state set required to define the starting state is determined directly from the first data subset.
In accordance with a fourteenth embodiment of the current invention there is provided an apparatus for encoding a raw data set of K ordered symbols comprised of four elements. The first element is a recursive systematic convolutional (RSC) encoder having a memory size of at least one and a repetition period p. The second element is a buffer means for dividing the raw data set into first and second data subsets containing m and K-m ordered symbols respectively, where m is at least one and at most the memory size of the RSC encoder, and K-m is a multiple of p. The third element is a plurality P-1 of interleavers each for interleaving K-m ordered symbols, where P is a multiple of 2. The fourth element is a reset means for initializing the RSC encoder with a starting state based on the first data subset, such that the starting state uniquely corresponds to the first data subset, such that each interleaver interleaves a systematic set consisting of the second data subset to form P permutations of the systematic set, such that each symbol in each permutation is paired with the same symbol in a different permutation at a distance of an integer multiple of p and that the RSC encoder encodes a contiguous block consisting of said P permutations to generate P parity sets of ordered symbols, thereby forcing an ending state to be the same as the starting state. An embodiment of this fourteenth aspect of the current invention is a turbo encoder as described above, wherein m equals the memory size of the RSC encoder, and the RSC encoder has a state defined by a state set of m ordered state symbols, such that the state set required to define the starting state is determined directly from the first data subset.
In accordance with a fifteenth embodiment of the current invention there is provided an apparatus for decoding a set of ordered samples representing a set of ordered symbols encoded according to the method described in the first aspect of the present invention, comprised of three elements. The first element is a data estimator for obtaining an estimate of the second data subset. The second element is a state estimator for obtaining an estimate of the starting state. The third element is a mapper responsive to the state estimator to map the estimate of the starting state to an estimate of the first data subset.
In accordance with a sixteenth embodiment of the current invention there is provided an apparatus for decoding a set of ordered samples representing a set of ordered symbols encoded according to the method described in the first embodiment of the first aspect of the current invention, comprised of three elements. The first element is a data estimator for obtaining an estimate of the second data subset. The second element is a state estimator for obtaining an estimate of the starting state. The third element is a mapper responsive to the state estimator to map the estimate of the starting state to an estimate of the first data subset.
In accordance with a seventeenth embodiment of the current invention there is provided an apparatus for decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the second aspect of the current invention, comprised of three elements. The first element is a data estimator for obtaining an estimate of the second data subset using a method of iterative data estimation. The second element is a state estimator for obtaining an estimate of the total starting state, consisting of estimates of all individual starting states of the P RSC encoders. The third element is a mapper responsive to the state estimator to map the estimate of the total starting state to an estimate of the first data subset.
In accordance with an eighteenth embodiment of the current invention there is provided an apparatus for decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the third embodiment of the current invention comprised of three elements. The first element is a data estimator for obtaining an estimate of the second data subset using a method of iterative data estimation. The second element is a state estimator for obtaining an estimate of the starting state. The third element is a mapper responsive to the state estimator to map the estimate of the starting state to an estimate of the first data subset.
In accordance with a nineteenth embodiment of the current invention there is provided an apparatus for decoding a set of ordered samples representing a set of K ordered symbols encoded according to the method described in the fourth aspect of the current invention, comprised of three elements. The first element is a data estimator for obtaining an estimate of the second data subset using a method of iterative data estimation. The second element is a state estimator for obtaining an estimate of the starting state. The third element is a mapper responsive to the state estimator to map the estimate of the starting state to an estimate of the first data subset.